//反转字符串中的单词
/*给你一个字符串 s ，请你反转字符串中 单词 的顺序。

单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。

返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。

注意：输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。*/
class Solution {
public:
    string reverseWords(string s) {
        string ret;
        vector<string> arr;
        int left = 0, right = 0;
        while (s[right] == ' ') {
            right++;
        }
        left = right;
        // 去除前导空格
        while (right <= s.size()) {
            if (s[right] == ' ' || (right == s.size() && s[right - 1] != ' ')) {
                //  ret += string(s.begin() + left, s.begin() + right);
                // ret += " ";
                arr.push_back(string(s.begin() + left, s.begin() + right));
                while (right < s.size() && s[right] == ' ') {
                    right++;
                }
                left = right;
            }
            right++;
        }
        //   ret.pop_back();
        while (arr.size()) {
            ret += arr.back();
            arr.pop_back();
            if (arr.size() >= 1)
                ret += " ";
        }
        return ret;
    }
};


//插入区间
/*给你一个 无重叠的 ，按照区间起始端点排序的区间列表 intervals，其中 intervals[i] = [starti, endi] 表示第 i 个区间的开始和结束，并且 intervals 按照 starti 升序排列。同样给定一个区间 newInterval = [start, end] 表示另一个区间的开始和结束。

在 intervals 中插入区间 newInterval，使得 intervals 依然按照 starti 升序排列，且区间之间不重叠（如果有必要的话，可以合并区间）。

返回插入之后的 intervals。

注意 你不需要原地修改 intervals。你可以创建一个新数组然后返回它。

 */
 class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals,
                               vector<int>& newInterval) {
        vector<vector<int>> ret;
        if (intervals.size() == 0) {
            ret.push_back(newInterval);
            return ret;
        }
        // ret.push_back(intervals[0]);
        bool floag = true;
        if (intervals[0][0] > newInterval[0]) {
            floag = false;
            ret.push_back(newInterval);
        } else
            ret.push_back(intervals[0]);

        for (int i = 0; i < intervals.size(); i++) {
            if (floag) {
                if (newInterval[0] >= ret[ret.size() - 1][0] &&
                    newInterval[0] <= ret[ret.size() - 1][1]) {
                    floag = false;
                    if (newInterval[1] > ret[ret.size() - 1][1])
                        ret[ret.size() - 1][1] = newInterval[1];
                } else if (newInterval[0] < intervals[i][0]) { // &&
                    // newInterval[1] >= intervals[i][0] &&
                    // newInterval[1] <= intervals[i][1]) {
                    floag = false;
                    ret.push_back(newInterval);
                }
            }
            if (ret[ret.size() - 1][1] < intervals[i][0])
                ret.push_back(intervals[i]);
            else if (intervals[i][1] > ret[ret.size() - 1][1])
                ret[ret.size() - 1][1] = intervals[i][1];
        }
        if (floag) {
            if (newInterval[0] >= ret[ret.size() - 1][0] &&
                newInterval[0] <= ret[ret.size() - 1][1]) {
                floag = false;
                if (newInterval[1] > ret[ret.size() - 1][1])
                    ret[ret.size() - 1][1] = newInterval[1];
            } else
                ret.push_back(newInterval);
        }
        return ret;
    }
};